package com.Test;

import java.util.ArrayList;
import java.util.List;

public class Test03 {
    public static void main(String[] args) {

        int[] arr = {70, 95, 120, 140, 160, 175, 190, 205, 220, 230, 245, 255, 265, 270, 280};
        int target = 1000;

        int closestSum = Integer.MAX_VALUE;
        List<Integer> closestCombination = new ArrayList<>();

        // 递归生成所有五元组的组合
        generateCombination(arr, target, 0, new ArrayList<>(), closestSum, closestCombination);

        System.out.println("五个值相加结果最接近901的组合为" + closestCombination + "，它们的和为" + closestSum);
    }

    private static void generateCombination(int[] arr, int target, int index, List<Integer> currentCombination, int closestSum, List<Integer> closestCombination) {
        if (currentCombination.size() == 5) {
            int total = calculateSum(currentCombination);
            if (total == target) {
                closestCombination = new ArrayList<>(currentCombination);
            } else if (Math.abs(total - target) < Math.abs(closestSum - target)) {
                closestSum = total;
                closestCombination = new ArrayList<>(currentCombination);
            }
            return;
        }

        for (int i = index; i < arr.length; i++) {
            currentCombination.add(arr[i]);
            generateCombination(arr, target, i + 1, currentCombination, closestSum, closestCombination);
            currentCombination.remove(currentCombination.size() - 1);
        }
    }

    private static int calculateSum(List<Integer> combination) {
        int sum = 0;
        for (int num : combination) {
            sum += num;
        }
        return sum;
    }
}
